package lcs;

import java.util.List;

public class Lcs {
	private int[][] matrix_lcs;
	private String[][] matrix_path_lcs;
	private List<String> stringsatu;
	private List<String> stringdua;

	/**
	 * Construct lcs -> the lcs matrix will be built
	 */
	public Lcs(List<String> stringsatu, List<String> stringdua) {
		this.stringsatu = stringsatu;
		this.stringdua = stringdua;

		/**
		 * new int[y][x]
		 * 
		 * x = length of stringsatu y = length of stringdua
		 */
		this.matrix_lcs = new int[this.stringdua.size() + 1][this.stringsatu.size() + 1];
		this.matrix_path_lcs = new String[this.stringdua.size() + 1][this.stringsatu.size() + 1];

		/**
		 * Inisialisasi 0
		 */
		for (int y = 0; y <= this.stringdua.size(); y++) {
			this.matrix_lcs[y][0] = 0;
		}
		for (int x = 0; x <= this.stringsatu.size(); x++) {
			this.matrix_lcs[0][x] = 0;
		}

		/**
		 * isi tengahnya matrix lcs
		 */
		for (int y = 1; y <= this.stringdua.size(); y++) {
			for (int x = 1; x <= this.stringsatu.size(); x++) {
				if (stringsatu.get(x-1).equals(stringdua.get(y-1))) {
					this.matrix_lcs[y][x] = 1 + this.matrix_lcs[y - 1][x - 1];
				} else {
					int masuk = 0;
					if (this.matrix_lcs[y - 1][x] > this.matrix_lcs[y][x - 1]) {
						masuk = this.matrix_lcs[y - 1][x];
					} else {
						masuk = this.matrix_lcs[y][x - 1];
					}
					this.matrix_lcs[y][x] = masuk;
				}
			}
		}
		built_matrix_path();
	}

	/**
	 * built matrix path of the 2 string : * ^ <
	 */
	public void built_matrix_path() {
		/**
		 * Inisialisasi 0
		 */
		for (int y = 1; y <= stringdua.size(); y++) {
			this.matrix_path_lcs[y][0] = stringdua.get(y-1);
		}
		for (int x = 1; x <= stringsatu.size(); x++) {
			this.matrix_path_lcs[0][x] = stringsatu.get(x-1);
		}

		this.matrix_path_lcs[0][0] = "0";

		/**
		 * isi tengahnya matrix lcs
		 */
		for (int y = 1; y <= stringdua.size(); y++) {
			for (int x = 1; x <= stringsatu.size(); x++) {
				if (stringsatu.get(x-1).equals(stringdua.get(y-1))) {
					this.matrix_path_lcs[y][x] = "*";
				} else if (this.matrix_lcs[y - 1][x] >= this.matrix_lcs[y][x - 1]) {
					this.matrix_path_lcs[y][x] = "^";
				} else {
					this.matrix_path_lcs[y][x] = "<";
				}
			}
		}
		similarity();
	}

	/**
	 * count similarity of 2 string
	 * @return similarity
	 */
	public double similarity() {
		String hasil = "";
		int y = this.stringdua.size();
		int x = this.stringsatu.size();
		double sim = 0;
		double numbOfReplacement=0;
		double jum=0;

		while (y > 0 || x > 0) {
			if (matrix_path_lcs[y][x] == "*") {
				hasil = matrix_path_lcs[y][x] + hasil;
				y = y - 1;
				x = x - 1;
				numbOfReplacement++;
			} else if (matrix_path_lcs[y][x] == "^") {
				hasil = matrix_path_lcs[y][x] + hasil;
				y = y - 1;
			} else if (matrix_path_lcs[y][x] == "<"){
				hasil = matrix_path_lcs[y][x] + hasil;
				x = x - 1;
			} else {
				break;
			}
			jum++;
		}
		sim = numbOfReplacement/jum;
//		System.out.println("Replacement = "+numbOfReplacement);
//		System.out.println("Jum = "+jum);
		System.out.println("Substring yang berurutan (in symbol) : "+hasil);
		System.out.println("Similarity : "+sim);
		return sim;
	}

	/*
	 *================================================================METHOD PRINT================================================================
	 */
	
	/**
	 * print subsequence string
	 * 
	 */
	public void print_hasil_path() {
		String hasil = "";
		int y = this.stringdua.size();
		int x = this.stringsatu.size();

		while (y > 0 || x > 0) {
			// System.out.print(y+","+x);
			if (matrix_path_lcs[y][x] == "*") {
				// System.out.println(" masuk *, huruf : "+path_lcs[y][0]);
				hasil = matrix_path_lcs[y][0] + hasil;
				y = y - 1;
				x = x - 1;
			} else if (matrix_path_lcs[y][x] == "^") {
				// System.out.println(" masuk ^");
				y = y - 1;
			} else {
				// System.out.println(" masuk <");
				x = x - 1;
			}
		}
		 System.out.print("Substring yang berurutan : "+hasil);
	}

	/**
	 * print matrix lcs
	 */
	public void print_matrix_lcs() {
		System.out.println("Matrix lcs : ");
		for (int y = 0; y <= this.stringdua.size(); y++) {
			for (int x = 0; x <= this.stringsatu.size(); x++) {
				System.out.print(this.matrix_lcs[y][x] + "	");
			}
			System.out.println();
		}
	}

	/**
	 * print matrix path
	 */
	public void print_matrix_path() {
		System.out.println("Matrix path : ");
		/**
		 * print matrix path_lcs
		 */
		for (int y = 0; y <= this.stringdua.size(); y++) {
			for (int x = 0; x <= this.stringsatu.size(); x++) {
				System.out.print(this.matrix_path_lcs[y][x] + "	");
			}
			System.out.println();
		}
	}

	/**
	 * print array
	 * @param array that will be printed
	 */
	public void printArray(List<String> array) {
		for (int k = 0; k < array.size(); k++) {
			System.out.print(array.get(k) + ' ');
		}
	}
}
